1. Technical Field
The present invention relates to a method for controlling the rate of data transmitted to a user on a communications link, and in particular to a method of resource control wherein resource requests from a user to a service provider are determined in response to the amount of congestion on the communications link.
2. Related Art
The last two decades have seen the introduction of so-called ‘integrated’ networks, such as asynchronous transfer mode (ATM) and Internet Protocol (IP) networks, which are designed to carry both computer communications and telephony. The capacity of those networks needs to be allocated between users who require a constant bit-rate for the duration of a communication (e.g. telephone users), those who can tolerate some variation in the bit-rate supplied to them by the network (e.g. those transferring web-pages, software or e-mails), and those users who can tolerate less variation in the bit-rate supplied to them by the network (e.g. those transferring video clips or other real time applications).
To deal with different user's requirements, integrated networks offer their users the ability to specify which service they wish to receive from the network (which, being an integrated network, can offer a plurality of different services). This specification can be made once at the start of a communication (the normal procedure in networks offering a connection-oriented service, such as ATM networks) and/or repeatedly during a communication.
As mentioned, an Internet Protocol network is one type of integrated network. An IP network can offer a constant bit-rate service type (using the Resource Reservation Protocol (RSVP)), and a best efforts service type. Another service type gives packets sent by one class of users priority over packets sent by another class of user. Using RSVP, a user can additionally specify the amount of bandwidth he or she wishes to have available.
Where a person has to make such a service specification many times because he or she is involved in a number of different communications and/or has to make a plurality of service specifications during a communication, it is beneficial if that specification is made on that person's behalf by a computer programmed to act as that person's agent.
The present invention concerns how the computer acting as an agent determines the data rate request for the user.
During the last five years not only has the amount in Internet traffic increased dramatically, but there has also been a significant diversification in the type of traffic flowing through computer networks. Until fairly recently, file transfer, email and simple web traffic formed the almost all the data flows on the Internet. Now applications may include multi-party and/or multi media data transmission. Such applications include “real-time” audio and video, interactive games, instant messaging, multi-party virtual worlds, network games, auctions, audio and video-conferencing and IP telephony.
In view of the increase in data transmission, efficient control and management of the network resources is becoming increasing important. One of the problems faced by network users and service providers is congestion, a situation in which there is too much data for the network to handle. The consequence of which is delays or even loss of data.
Traditionally, rate control in the Internet is taken care of by the Transmission Control Protocol (TCP). TCP is described in many references places, for example, “Fred Halsall, Data communications, computer networks and open systems, 6th ed., Addison-Wesley, 1995. TCP is a window based rate control algorithm, i.e. window based rate control is achieved by limiting the amount of data that can be in the network at any one time. TCP is stable and normally makes fairly efficient use of the available bandwidth, and distributes network resources fairly between different users. For file transfer and email, TCP performs well because, provided the file or email arrives within a reasonable time at its destination, it is not important at which rate the data was transmitted. However, TCP rate control gives rise to fluctuations in the transfer rate that are unacceptable for applications where the rate of data transmission is important, for example, real time applications, such as video and audio streaming. The reason for this is that if a single packet is lost the congestion window is halved. Further TCP guarantees that lost packets will be retransmitted until they arrive at the receiver. For some applications including real-time multimedia applications, this is not necessary. Problems with rate fluctuations which occur in networks running TCP have made it necessary to develop alternative rate control algorithms. It is believed that in time TCP will become a less preferred option, as it becomes less able to deal with the greater variety of services users demand.
Further, as congestion on the Internet increases, network managers are looking for alternative ways to manage it. Also, multimedia multi-party internet protocol (IP) applications, such as those mentioned above, can be very demanding in terms of their Quality of Service (QoS) requirements. Standards are being developed to ensure that network resources can be applied where they are most needed. However, problems still surround how the demand for different classes of QoS should be managed.
One solution to this problem may be congestion based pricing. The underlying idea being to charge users or, on a more abstract level, to charge applications. The charge may be either in terms of real currency or in some other terms, for example fictional currency. The charge is made for the network resources used. Also the charge increases depending on the level of network congestion. When bandwidth becomes scarce, the charge will increase, when congestion reduces the charge is decreased. This gives users, or applications, the incentive to back off the network at times of network congestion. Congestion based pricing is discussed by F. P. Kelly in “Charging and rate control for elastic traffic”, European Transactions on Telecommunications, vol. 8, pp33-37, January 1997.
Conventional rate control techniques are based on variables which reflect network performance, such variables include packet loss or roundtrip time. Price based approaches exploit “shadow prices” (an expression borrowed from economics which is applied to situations where actual prices cannot be charged, or where actual prices do not reflect the real sacrifice made when some activity is pursued. Shadow prices are used in valuing any item, such as a network resource, which is implicitly rationed or constrained in some way.) and user determined policies that specify how much the user values the data rate they get from the network. One way of expressing this variable is the user's willingness to pay for a particular service.
One such priced based technique for managing congestion is discussed in “F P Kelly, A K Maulloo, and D K H Tan, Rate control for communication networks: Shadow prices, proportional fairness and stability, Journal of the Operational Research Society 49 (1998), no. 3, 237-252”. In this paper, Kelly et al propose an “equation based algorithm”. Equation based algorithms are so called because they differ from window based algorithms, such as TCP, in that the sending rate is determined directly (without any other external constraints) using a mathematical equation. Contrary to window based rate control, equation based rate control does not place an explicit limit on the amount of outstanding data (data that has left the sender, but has not arrived at the receiver yet). At present, TCP, a window based algorithm, is not able to support such alternative equation based algorithms for rate control.
The equation based rate control algorithm proposed by Kelly et al is known as the “primal” algorithm. The primal algorithm determines the request for a data rate which a user sends to his service provider, when requesting a download of data. The primal algorithm is an adaptive system which takes user determined parameters, such as the user's willingness to pay for a service together with network manager determined parameters, such as the price charged by the resource per unit flow, and network determined parameters, such as the transfer rate of the flow along a particular route and the congestion price, to determine the sending rate request which the user sends to his service provider.
The primal algorithm has been shown to be stable. However, the rate of convergence, that is the rate at which the algorithm reaches a stable rate, is a particular problem with the primal algorithm. This causes problems in particular, at the beginning of a download, where it takes the primal algorithm too long to go from a very low data rate to the desired data rate, and in situations where congestion is to be avoided, where the user desires a relatively low data rate, with however, little variation.
The present invention provides a solution to the problems identified above with respect to resource control in data transmission.